package q761_makeLargestSpecial;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    /*
    此题首先需要考虑题意：对于特殊字符串的定义 也就是需要在一个满足1的数量等于0的数量的字符串中
    找出哪些字符串满足是特殊字符串 然后将其任意交换
    可以这样理解：
    0 和 1 的数量相等。 → “右括号” 数量和 “左括号” 相同
    二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。→ “右括号” 必须能够找到一个 “左括号” 匹配
    那么题目就变成：选择 S 中的两个 相邻 的 有效的括号字符串，然后交换即可。
    步骤就变为：
    1 将字符串拆分成一段或几段 “不可拆分的有效的括号字符串”。
    2 将每一段 内部 的子串（也是 “有效的括号字符串”）分别重新排列成字典序最大的字符串（解决子问题）。
    3 由于 每一对相邻的段都可以交换，因此无限次交换相当于我们可以把各个段以 任意顺序 排列。我们要找到字典序最大的排列。

    显然 在进行排列时 只需要字符串的字典序大于另一个字符串 我们就将其排在前面 就能够使得组合字符串的字典序最大
    例如 1100 和 10 两个字符串 1100的字典序更大 我们把它放在前面 能够构成的字符串字典序就更大
     */
    public String makeLargestSpecial(String s) {
        if (s.length() <= 2) return s;
        List<String> specials = new ArrayList<>();
        for (int i = 0, count = 0, last = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') ++count;
            else --count;
            if (count == 0) {
                specials.add("1" + makeLargestSpecial(s.substring(last + 1, i)) + "0");
                last = i + 1;
            }
        }
        // 注意有些写法是相同的 例如下面的排序 可以直接用字符串自带的方法sort，其中传入一个接口reverseOrder即为倒序排序
        // Collections.sort(subs, (a, b) -> b.compareTo(a));
        specials.sort(Comparator.reverseOrder());
        StringBuilder sb = new StringBuilder();
        // for (String sub : subs) sb.append(sub);
        // 用流的方式可以直接拼接所有字符串
        specials.forEach(sb::append);
        return sb.toString();
    }
}
